package com.dp.numTrees;

/**
 * @author zhaiyj
 * @date 2019/8/12 9:07
 * @description
 */
public class Solution {

    public static void main(String[] args) {
        int n = 3;
        numTrees(n);
    }

    public static int numTrees(int n) {

        long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int)C;

//        int[] G = new int[n + 1];
//        G[0] = 1;
//        G[1] = 1;
//
//        for (int i = 2; i <= n; i++) {
//            for (int j = 1; j <= i; j++) {
//                G[i] += G[j-1] * G[i-j];
//            }
//        }
//        return G[n];
    }


}
